package ljl.alg.jianzhioffer.round2;

import commons.TreeNode;

public class _26_is_substructure {
    
    /**
     * b 是 a 的子结构，那从某个点开始，b 必须和 a 都一样
     * 先找 a 和 b 相等的那个点，然后开始判断
     * 找这个点的过程是 dfs
     *
     * 居然蒙出来了
     *
     * 看了看答案确实不太聪明
     * */
    public boolean isSubStructure3(TreeNode A, TreeNode B) {
        if (B == null) return false;
        dfs(A, B);
        return yes;
    }
    boolean yes;
    void dfs(TreeNode a, TreeNode b) {
        if (a == null) return;
        if (a.val == b.val)
            yes = same(a, b);
        if (!yes)
            dfs(a.left, b);
        if (!yes)
            dfs(a.right, b);
    }
    
    boolean same(TreeNode a, TreeNode b) {
        if (b == null)
            return true;
        if (a == null)
            return false;
        if (a.val != b.val)
            return false;
        return same(a.left, b.left) && same(a.right, b.right);
    }
    
    /**
     * 路飞
     * */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return A != null && B != null && (recur(A, B) || isSubStructure3(A.left, B) || isSubStructure3(A.right, B));
    }
    boolean recur(TreeNode a, TreeNode b) {
        if (b == null) return true;
        if (a == null || a.val != b.val) return false;
        return recur(a.left, b.left) && recur(a.right, b.right);
    }
}
